#ifndef _INVERSION_VECTOR_H
#define _INVERSION_VECTOR_H

#ifdef __cplusplus
extern "C" {
#endif

// This returns an unsigned int array of size len which is the inversion vector of seq,
// i.e., a[i] is equal to the number of elements a[j] where j<i and seq[j]>seq[i].
// Memory for the array is acquired with malloc and may be released in the usual way.
unsigned int *make_inversion_vector2(const unsigned int *seq, unsigned int len, unsigned int max_value);
unsigned int *make_inversion_vector(const unsigned int *seq, unsigned int len);

unsigned int *make_reverse_inversion_vector2(const unsigned int *seq, unsigned int len, unsigned int max_value);
unsigned int *make_reverse_inversion_vector(const unsigned int *seq, unsigned int len);

// Internal recursive function that computes the sorted inversion vector, from which the inversion vector can be derived.
void compute_sorted_inversions(unsigned int *data, unsigned int *sorted_inversions, unsigned int *temp, unsigned int begin, unsigned int end);

// Internal function for inverting the IV that works like compute_sorted_inversions().
void invert_inversion_vector_recursive(unsigned int *inversions, unsigned int *index, unsigned int *temp, unsigned int begin, unsigned int end);

unsigned int *invert_inversion_vector(const unsigned int *inversions, unsigned int len);
unsigned int *invert_reverse_inversion_vector(const unsigned int *rsiv, unsigned int len);

#ifdef __cplusplus
}
#endif

#endif
